2774. 数组上界(二分和双指针)

2774. 数组的上界

interface Array<T> {
  upperBound(target: number): number
}

/**
 * 二分法
 * 时间复杂度: O(log n)
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function (target: number): number {
    let left = 0, right = this.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (this[mid] === target) {
            result = mid;
            left = mid + 1; // 向右查找更新更大的索引
        } else if (this[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

/**
 * 遍历
 * 时间复杂度: O(n) 最坏情况下需要遍历整个字符串
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function(target) {
  for(let i = this.length - 1; i >= 0; i--) {
    if(target === this[i]) return i
  }
  return -1;
};

/**
 * 双指针遍历
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
Array.prototype.upperBound = function (target): number {
  if (this.length == 0) return -1
  let i = 0
  let l = this.length - 1
  let upperIndex = -1
  while (i <= l) {
    if (this[l] === target) return l
    if (this[i] > target) return upperIndex;
    if (this[i] === target) {
      if (i > upperIndex) upperIndex = i
    }
    i++;
    l--;
  }
  return upperIndex;
}

/**
 * js 数组原生方法
 * 时间复杂度: O(n) 最坏情况下需要遍历整个字符串
 * 空间复杂度: O(1) 没有使用额外空间
 */
Array.prototype.upperBound = function(target) {
  return this.lastIndexOf(target);
};

四种写法对比

“数组上界”这里指的是找到 target 在数组中最后一次出现的索引。四种写法都能完成，但适用前提并不一样。

二分法（O(log N)）依赖数组有序，每次折半缩小搜索范围。找到 target 后不立即返回，而是继续向右搜索，这是上界查找和普通查找最关键的区别。

双指针（O(N)）从两端同时扫描。右指针遇到 target 直接返回（因为从右往左第一个遇到的就是最右的），这比单向扫描快一些，但最坏情况仍然是 O(N)。不依赖数组有序。

逆序遍历（O(N)）从末尾向前扫，第一个匹配的就是答案。同样是 O(N)，也不依赖有序。

lastIndexOf（O(N)）是原生实现，写法最短。如果只关心结果，不关心手写过程，直接用它也成立。

实际选择

• 确认数组有序：二分，O(log N)
• 数组无序或前提不明确：lastIndexOf
• 需要手写过程：二分里要明确“找到后继续向右”